(* ======================================================================== *)
(*             Basic Multivariate Polynomial Algebra over Q[\vec{x}]        *)
(*                                                                          *)
(* by G.O.Passmore, Cambridge Computer Laboratory and LFCS, Edinburgh, 2011 *)
(* Contact: (e) grant.passmore@cl.cam.ac.uk   (w) www.cl.cam.ac.uk/~gp351/. *)
(* ======================================================================== *)

signature Algebra = 
sig

(* Var ID type *)

type var_id;

(* Var-power type *)

type vp;

(* Power-product type *)

type pp;

(* Monomial type *)

type mono;

(* Polynomial type *)

type poly;

(* Monomial multiplication *)

val m_mult : mono * mono -> Rat.rat * vp list;

(* Monomial, Polynomial multiplication *)

val mp_mult : mono * poly -> poly;

(* Monomial negation *)

val m_neg : mono -> Rat.rat * pp;

(* Multivariate total degree of monomial *)

val m_deg : mono -> int;

(* Degree reverse lexicographic ordering on monomials *)

val m_lt : mono * mono -> bool;

(* Convert monomial to polynomial *)

val poly_of_mono : mono -> poly;

(* Convert Rat.rat to polynomial *)

val poly_of_rat : Rat.rat -> poly;

(* Make a polynomial monic (in the context of an implicit = 0) *)

val p_monic : poly -> poly;

(* Compute the LCM of two power-products in canonical form *)

val pp_lcm : pp * pp -> pp;

(* Divide one power-product by another *)

val pp_div : pp * pp -> pp;

(* Does one power-product divide another? *)

val pp_divides : pp * pp -> bool;

(* Given a polynomial, return its head power-product. *)

val p_hpp : poly -> pp;

(* Given a polynomial, return its head monomial. *)

val p_hm : poly -> mono;

(* Divide one monomial by another *)

val m_div : mono * mono -> mono;

(* Polynomial + *)

val p_sum : poly * poly -> poly;

(* Polynomial unary - *)

val p_neg : poly -> poly;

(* Polynomial subtraction *)

val p_sub : poly * poly -> poly;

(* Polynomial multiplication *)

val p_mult : poly * poly -> poly;

(* Are two polynomials equal? *)

val p_eq : poly * poly -> bool;

(* Power-product to string *)

val pp_toString : (int * int) list -> string;

(* Monomial to string *)

val m_toString : mono -> string;

(* Polynomial to string *)

val p_toString : mono list -> string;

(* Zero polynomial *)

val p_zero : poly;

(* One polynomial *)

val p_one : poly;

end;
